/**
 * 最长无重复子数组
 *
 * 描述
 * 给定一个长度为n的数组arr，返回arr的最长无重复元素子数组的长度，无重复指的是所有数字都不相同。
 * 子数组是连续的，比如[1,3,5,7,9]的子数组有[1,3]，[3,5,7]等等，但是[1,3,7]不是子数组
 *
 * 数据范围：
 * 0≤arr.length≤10^5
 * 0<arr[i]≤10^5
 */

import java.util.HashSet;
import java.util.Set;

/**
 * 使用双指针和 set 解决, 我们将每个遍历的数字存入 set 中
 * 要是有重复的我们就利用双指针将 set 中的数字, 按照顺序一个一个
 * remove, 直到和 right 没有重复为止, 然后我们在将 right 加入
 * set, 每次一都求一下 最大长度就可以了
 *
 * 本质也就是为了遍历位置的值让出位置
 * 时间复杂度 : O(n ^ 2)
 * 空间复杂度 : O(n)
 */

public class Main {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int maxLength (int[] arr) {
        // write code here

        // set
        Set<Integer> hash = new HashSet<>();
        int n = arr.length;

        // 最终结果
        int res = 0;

        // 双指针
        for (int left = 0, right = 0; right < n; right++) {

            // 遍历位置的值
            int x = arr[right];

            // 要是有重复, 按照 left 删除数字, 直到没有重复为止
            while (left < right && hash.contains(x)) {
                hash.remove(arr[left]);
                left++;
            }

            // 再将本位置的值加入 set
            hash.add(x);

            // 求最大值
            res = Math.max(res, hash.size());
        }

        // 返回结果
        return res;
    }
}